package com.fanco.learn_datastruct_leetcode.leetcode;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * @author qiaowang 2021/7/6
 */
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Day11 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));

        ListNode head = solution.removeNthFromEnd(listNode, 2);
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }

    }

    private static class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0,head);
            int length = getLength(head);

            ListNode cur = dummy;

            // 需要去掉加上的头结点。
            for (int i = 1 ; i < length -n+1 ;i ++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
            ListNode ans = dummy.next;
            return ans;
        }

        public int getLength (ListNode head) {
            int num = 0;
            while (head != null) {
                num++;
                head = head.next;
            }
            return num;
        }
    }
}
